In computer graphics applications, rendering characters is an important branch. Two-dimensional characters are generally formed by quadratic Bezier curves, cubic Bezier curves, and elliptical curves etc., in a two-dimensional plane.
It is inefficient, for a Graphics Display Controller (GDC) chip, to render curves pixel by pixel by tracking along the curves. With appropriate precision, it is reasonable to approximate a curve with straight lines. It is a tradeoff between precision and speed. For many applications of GDC chips, speed overwhelms precision, such as car navigation, mobile phone, and amusement displayer.
Approximating a curve with straight lines needs to firstly subdivide the curve with subdividing points, then calculate coordinates of the subdividing points, and finally connect adjacent subdividing points via straight lines. It is a long existing problem to approximate a curve. There exist many solutions to approximate Bezier curves, such as direct method, recursive subdivision, forward differencing, and hybrid method. However, these methods are not fast enough.
As Bezier curves are commonly represented by polynomials of parameter t (for example, x(t)=a·t2+b·t+c, y(t)=d·t2+e·t+f for quadratic Bezier curve, where the coefficients a, b, c, d, e, and f can be calculated by control points of the quadratic Bezier curve), the coordinate values of each subdividing point can be calculated directly, given the parameter t at each subdividing point. Although this method is simple and direct, it needs too many multiplications for each subdividing point.
Recursive subdivision is a recursive procedure, to find step by step subdividing points by calculating the middle points on each edge of a control polygon. Connecting adjacent subdividing points will form straight lines. Setting an appropriate threshold of flatness, the straight lines will approximate a curve with reasonable precision. However, the recursive procedure and calculating flatness will take a large amount of time.
Forward differencing is suitable for Bezier curves. The coordinate values of a next subdividing point can be got by adding the coordinate values of a previous subdividing point with difference values. With a fixed step, the coordinate values of each subdividing point can be calculated by just several addition operations. Therefore, the speed is very high. However, the number of the subdividing points (i.e. the step) needs to be determined before calculating the coordinates.
The hybrid method combines recursive subdivision and forward differencing together. It first uses recursive subdivision and flatness to obtains the parameter of each subdividing point, and then uses forward differencing to calculate the coordinate values of each subdividing point. This method is complex for implementation.
Therefore, a method and/or apparatus for approximating a curve, used in curve rendering and more efficient than the abovementioned methods, are needed.